import java.util.*;

public class test_1_8 {
//    1.平衡二叉树
//    给定一个二叉树，判断它是否是高度平衡的二叉树。
//    示例 1：
//    输入：root = [3,9,20,null,null,15,7]
//    输出：true
//    示例 2：
//    输入：root = [1,2,2,3,3,null,null,4,4]
//    输出：false
//    示例 3：
//    输入：root = []
//    输出：true

//    public static boolean isBalanced(TreeNode root) {
//        if(root==null){
//            return true;
//        }
//        int left=maxdepth(root.left);
//        int right=maxdepth(root.right);
//        return Math.abs(left-right)<2
//                &&isBalanced(root.left)
//                &&isBalanced(root.right);
//    }
//    public static int maxdepth(TreeNode root){
//        if(root==null){
//            return 0;
//        }
//        int left=maxdepth(root.left);
//        int right=maxdepth(root.right);
//        return (left>right)?(left+1):(right+1);
//    }


//    public static boolean isBalanced2(TreeNode root){
//        return maxDepth2(root)>=0;
//    }
//    public static int maxDepth2(TreeNode root){
//        if(root==null){
//            return 0;
//        }
//        int lefth=maxDepth2(root.left);
//        if(lefth<0){
//            return -1;
//        }
//        int righth=maxDepth2(root.right);
//        if(righth<0){
//            return -1;
//        }
//        if(Math.abs(lefth-righth)<=1){
//            return Math.max(lefth,righth);
//        }else{
//            return -1;
//        }
//    }



//    2.翻转二叉树
//    给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
//    示例 1：
//    输入：root = [4,2,7,1,3,6,9]
//    输出：[4,7,2,9,6,3,1]
//    示例 2：
//    输入：root = [2,1,3]
//    输出：[2,3,1]
//    示例 3：
//    输入：root = []
//    输出：[]

//    public static TreeNode invertTree(TreeNode root) {
//        if(root==null){
//            return null;
//        }
//        TreeNode tmp=root.left;
//        root.left=root.right;
//        root.right=tmp;
//        invertTree(root.left);
//        invertTree(root.right);
//        return root;
//    }



//    3.对称二叉树
//    给你一个二叉树的根节点 root ， 检查它是否轴对称。
//    示例 1：
//    输入：root = [1,2,2,3,4,4,3]
//    输出：true
//    示例 2：
//    输入：root = [1,2,2,null,3,null,3]
//    输出：false

//    public static boolean isSymmetric(TreeNode root) {
//        if(root==null){
//            return true;
//        }
//        return isSymmetricChild(root.left,root.right);
//    }
//    public static boolean isSymmetricChild(TreeNode lefttree,TreeNode righttree){
//        if(lefttree!=null&&righttree==null||lefttree==null&&righttree!=null){
//            return false;
//        }
//        if(lefttree==null&&righttree==null){
//            return true;
//        }
//        if(lefttree.val!=righttree.val){
//            return false;
//        }
//        return isSymmetricChild(lefttree.left,righttree.right)&&isSymmetricChild(lefttree.right,righttree.left);
//    }



//    4.相同的树
//    给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
//    如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
//    示例 1：
//    输入：p = [1,2], q = [1,null,2]
//    输出：false
//    示例 2：
//    输入：p = [1,2,1], q = [1,1,2]
//    输出：false

//    public static boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p==null&&q!=null||p!=null&&q==null){
//            return false;
//        }
//        if(p==null&&q==null){
//            return true;
//        }
//        if(p.val!=q.val){
//            return false;
//        }
//        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
//    }




//    5.另一棵树的子树
//    给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
//    二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
//    示例 1：
//    输入：root = [3,4,5,1,2], subRoot = [4,1,2]
//    输出：true
//    示例 2：
//    输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
//    输出：false

//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        if(root==null||subRoot==null){
//            return false;
//        }
//        if(isSametree(root,subRoot)){
//            return true;
//        }
//        if(isSubtree(root.left,subRoot)){
//            return true;
//        }
//        if(isSubtree(root.right,subRoot)){
//            return true;
//        }
//        return false;
//    }
//    public static boolean isSametree(TreeNode p,TreeNode q){
//        if(p==null&&q!=null||p!=null&&q==null){
//            return false;
//        }
//        if(p==null&&q==null){
//            return true;
//        }
//        if(p.val!=q.val){
//            return false;
//        }
//        return isSametree(p.left,q.left)&&isSametree(p.right,q.right);
//    }



    //两种二叉树的层序遍历
    public void levelOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }


}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
